package leetcode_700;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;

/**
 *@author 周杨
 *TopKFrequentWords_692 找出给定单词中出现频率最高的K个单词 如果次数有相等的结果 那么按字典顺序输出
 *describe:AC 57% 用优先队列
 *2018年10月9日 下午2:30:58
 */
public class TopKFrequentWords_692 {
	static class Word{
		String elem;
		int count;
		public Word(String elem,int count) {
			this.elem=elem;
			this.count=count;
		}
	}
	public static void main(String[] args) {
		TopKFrequentWords_692 test=new TopKFrequentWords_692();
		test.topKFrequent(new String[] {"i", "love", "leetcode", "i", "love", "coding"}, 1);
		//test.topKFrequent(new String[] {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"}
		//, 4);
		 PriorityQueue<Word> queue=new PriorityQueue<Word>(new Comparator<Word>() {

				@Override
				public int compare(Word o1, Word o2) {
					if(o1.count<o2.count)
						return -1;
					else if(o1.count==o2.count)
						return o2.elem.compareTo(o1.elem);//那么比较字典顺序
					return 1;
				}
			});
		 Word word1=new Word("love", 1);
		 Word word2=new Word("i",1);
		 queue.offer(word1);
		 queue.offer(word2);
		 for(Word word:queue) {
			 System.out.println(word.elem);
		 }
	}
	
	
	/**
	 * describe:直接堆排序
	 * 2018年10月9日 下午2:29:56
	 */
	public List<String> topKFrequent_(String[] words, int k) {
        Map<String, Integer> m = new HashMap<>();
        for(String word : words) m.put(word, m.getOrDefault(word, 0) + 1);
        PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>(){
            @Override
            public int compare(Map.Entry<String, Integer> a, Map.Entry<String, Integer> b) {
                return a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue();
            }
        });
        for(Map.Entry<String, Integer> entry : m.entrySet()) {
            pq.add(entry);
        }
        List<String> ans = new ArrayList<>();
        while(k > 0) {
            ans.add(pq.remove().getKey());
            k--;
        }
        return ans;
    }
	
	
	/**
	 * describe:用堆实现 不知道哪里出了错
	 * 2018年10月9日 下午2:27:19
	 */
	public List<String> topKFrequent(String[] words, int k) {
		Map<String,Word> map=new HashMap<String,Word>();
        for(int i=0;i<words.length;++i) {
        	String word=words[i];
        	Word wd=map.get(word);
        	if(wd==null) {
        		wd=new Word(word, 1);
        	}
        	else
        		wd.count++;
        	map.put(word, wd);
        }
        PriorityQueue<Word> queue=new PriorityQueue<Word>(new Comparator<Word>() {

			@Override
			public int compare(Word o1, Word o2) {
				if(o1.count<o2.count)
					return -1;
				else if(o1.count==o2.count)
					return o1.elem.compareTo(o2.elem);//那么比较字典顺序
				return 1;
			}
		});
        for(Entry<String,Word> entry:map.entrySet()) {
        	Word word=entry.getValue();
        	if(queue.size()<k)
        		queue.add(word);
        	else {//看是否有必要调整堆
        		Word poll=queue.peek();
        		if(word.count>poll.count) {//比最小堆的顶还大 那么删除这个顶 重新构造堆
        			queue.poll();
        			queue.offer(word);
        		}
        		else if(word.count==poll.count) {
        			if(word.elem.compareTo(poll.elem)<0) {
        				queue.poll();
            			queue.offer(word);
        			}
        		}
        	}
        }
        List<String> res=new ArrayList<String>(queue.size());
        int index=queue.size()-1;
        for(int i=0;i<=index;++i) {
        	res.add(null);
        }
        for(Word word:queue)//其实就是从堆头开始放 所以我们要倒导入
        	res.set(index--, word.elem);       
        return res;
    }
	
	
	/*public List<String> topKFrequent1(String[] words, int k) {
		Map<String,Word> map=new HashMap<String,Word>();
        for(int i=0;i<words.length;++i) {
        	String word=words[i];
        	Word wd=map.get(word);
        	if(wd==null) {
        		wd=new Word(word, 1, i);
        	}
        	else
        		wd.count++;
        	map.put(word, wd);
        }
        PriorityQueue<Word> queue=new PriorityQueue<Word>(new Comparator<Word>() {

			@Override
			public int compare(Word o1, Word o2) {
				if(o1.count<o2.count)
					return -1;
				else if(o1.count==o2.count)
					return o1.index-o2.index;
				return 1;
			}
		});
        for(Entry<String,Word> entry:map.entrySet()) {
        	Word word=entry.getValue();
        	if(queue.size()<k)
        		queue.offer(word);
        	else {//看是否有必要调整堆
        		Word poll=queue.peek();
        		if(word.count>poll.count) {//比最小堆的顶还大 那么删除这个顶 重新构造堆
        			queue.poll();
        			queue.offer(word);
        		}
        		else if(word.count==poll.count) {
        			if(word.index<poll.index) {
        				queue.poll();
            			queue.offer(word);
        			}
        		}
        	}
        }
        List<String> res=new ArrayList<String>(queue.size());
        int index=queue.size()-1;
        for(int i=0;i<=index;++i) {
        	res.add(null);
        }
        for(Word word:queue)//其实就是从堆头开始放 所以我们要倒导入
        	res.set(index--, word.elem);       
        return res;
    }*/
}
